In a typical communications system, information is transmitted from a sender in the form of a communications signal representing the information. The communications signal typically is communicated to a receiving unit over a communications medium such as a radio, optical fiber, coaxial cable or similar link. Generally, the characteristics of the communications medium introduce disturbances such as noise, delay, and distortion in the communications signal. These disturbance can induce errors when recovering the original information from the communicated communications signal at the receiving unit.
Conventional responses to overcome this problem include increasing transmission power levels and introducing redundancy into the transmitted communications signal in order to increase the probability that the original information may be recovered. However, the ability to increase transmitter power may be limited due to power limitations of transmitter electronics, regulations on peak signal power levels and constraints on the power available for transmitting, for example, power supply limitations in devices such as mobile radiotelephones and satellites.
Redundancy may be introduced into a communications signal by using error control coding techniques. As illustrated in FIG. 1, a typical encoder 110 used in a digital communications system maps a group of k information symbols onto a group of k+n coded symbols, wherein the group of k+n coded symbols represents a "code word" in a set of code words and the additional n symbols in the code word represent redundant symbols. In general, the redundant n symbols can provide an additional "separation" between the words of the set of code words, thus allowing a receiver which receives a group of symbols over a noisy communications channel to more easily discriminate between words of the set of code words, typically by determining which member of the set of code words most closely resembles the received group of symbols.
Many error control codes are effective at correcting random errors, e.g., errors which affect individual symbols in a random distributed fashion, while others are effective at compensating for so-called "burst" errors, e.g., errors which persist over several consecutive symbols. To compensate for burst errors, many systems employ interleaving which reorders symbols in a stream such that burst errors are more randomly distributed, for example, by using a device which stores the symbol stream in rows and then retrieves the stored symbols by columns, such that the sequence retrieved from the device represents a reordering of the original input sequence. To combat random and burst errors, a system such as that illustrated in FIG. 2 may employ a cascade of a random error correction encoder 210 implementing a random error correction code such as a convolutional code, followed by an interleaver 220 which interleaves the symbols produced by the encoder 210 to help combat burst errors.
Another conventional approach uses a combination of random error correcting codes and interleaving to boost the random-error correcting ability in a so-called "turbo coding" scheme, as described in U.S. Pat. No. 5,446,747 to Berrou et al. As illustrated in FIG. 3, a source sequence of information symbols X.sub.k is encoded according to a first systematic code 310, for example, one of a family of recursive systematic codes described in "Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes" by Berrou et al., IEEE ICC Conference Record, 1993, pp.1064-1070. The source sequence X.sub.k is also interleaved in a interleaver 320 and then encoded according to a second systematic code 330, thus producing two encoded sequences Y.sub.1k, Y.sub.2k which are multiplexed with the source sequence X.sub.k and transmitted over a communications channel. As illustrated in FIG. 4, the received symbols are passed into a demultiplexer 410 to produce separate symbol sequences X.sub.k, Y.sub.1k, y.sub.2k. A first sequence y.sub.1k is fed into a first decoder 420, producing a log likelihood ratio LLR.sub.1 sequence. The log likelihood ratio sequence LLR.sub.1 is then interleaved in an interleaver 430 and fed into a cascade of a second decoder 430 and a deinterleaver 460 which produces a second log likelihood ratio sequence LLR.sub.2. The second log likelihood ratio sequence LLR.sub.2 is used by a decision device 470 to produce an estimated sequence of symbols d.sub.k which represents an estimate of the original sequence X.sub.k. The decoding system may also include feedback w.sub.2k from the second decoder 440 to the input of the first decoder 420 through a deinterleaver 450.
Although the interleaving systems described above can be effective at reducing burst errors, interleaving can introduce a significant delay into the coding and decoding of the communications signal. This processing delay can be highly undesirable in many applications, for example, by introducing annoying delays in two-way voice communications applications. In addition, interleaving can introduce additional complexity into the decoder design by requiring additional memory. Reducing the depth of the interleaving used can reduce delay, but reducing depth generally reduces the burst-error correcting capability of the coding scheme and may not significantly reduce decoder complexity.